package previous.Test_0217;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //猜数字大小
    int[][] memo;
    public int getMoneyAmount(int n) {
           memo=new int[n+1][n+1];
          return dfs(1,n);
    }
    public int dfs(int left,int right){
        if(left>=right) return 0;
        if(memo[left][right]!=0){
            return memo[left][right];
        }
        int ret=Integer.MAX_VALUE;
        for (int i = left; i <=right ; i++) {
            int x=dfs(left,i-1);
            int y=dfs(i+1,right);
            ret=Math.min(Math.max(x,y)+i,ret);
        }
        memo[left][right]=ret;
        return ret;
    }
    //矩阵中最长的递增路径
    int m,n;
    int[][] memo1;
    int ret;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    public int longestIncreasingPath(int[][] matrix) {
           m=matrix.length;
           n=matrix[0].length;
           memo1=new int[m+1][n+1];
        for (int i = 0; i < m+1; i++) {
            for (int j = 0; j <n+1 ; j++) {
                ret=Math.max(dfs(matrix,i,j),ret);
            }
        }

           return ret;
    }
    public int dfs(int[][] matrix,int i,int j){
        if(memo1[i][j]!=0){
            return memo1[i][j];
        }
        int path=1;
        for (int k = 0; k < 4; k++) {
            int x=dx[k]+i;
            int y=dy[k]+j;
            if(x>=0 && x<m && y>=0 && y<m && matrix[i][j]<matrix[x][y]){
                path=Math.max(path,dfs(matrix,x,y)+1);
            }
        }
        memo1[i][j]=path;
        return path;
    }
}
